package com.fanwei.afgorithm.code103;

import java.util.*;

/**
 * @author fanwei
 * @version 1.0.0
 * @ClassName 103.二叉树的锯齿形层序遍历（binary-tree-zigzag-level-order-traversal）
 * @Description https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/
 * @createTime 2021年11月25日 11:25:00
 */
public class BinaryTreeZigzagLevelOrderTraversal {

    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

    List<List<Integer>> res = new ArrayList<List<Integer>>();
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if (root == null)return res;
        List<TreeNode> nodes = new ArrayList<>();
        nodes.add(root);
        helper(nodes,1);
        return res;
    }

    private void helper(List<TreeNode> nodes, int index) {
        if (nodes.size() == 0) return;
        List<Integer> list = new ArrayList<>();
        List<TreeNode> currNodes = new ArrayList<>();

        for (int i = 0; i < nodes.size(); i++){
            TreeNode node = nodes.get(i);
            list.add(node.val);
            if (node.left != null){
                currNodes.add(node.left);
            }
            if (node.right != null){
                currNodes.add(node.right);
            }

        }

        //奇数层不用反转，偶数层要
        if (index % 2 == 0){
            Collections.reverse(list);
        }

        res.add(list);
        helper(currNodes, index + 1);
    }
}
// 这个和102题目基本一样的思路


